package 代码随想录.二叉树;

import java.util.*;

public class _9二叉树的最大深度 {
    /**
     * 104. 二叉树的最大深度
     * https://leetcode.cn/problems/maximum-depth-of-binary-tree/
     * 给定一个二叉树，找出其最大深度。
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * 说明: 叶子节点是指没有子节点的节点。
     */
    public int maxDepth(TreeNode root) {
        int res = 0;
        if(root==null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            int n = q.size();
            while (n-->0){
                TreeNode node = q.poll();
                if(node.left!=null)
                    q.offer(node.left);
                if(node.right!=null)
                    q.offer(node.right);
            }
            res++;
        }
        return res;
    }

    public int maxDepth2(TreeNode root) {
        if(root==null)
            return 0;
        return Math.max(maxDepth2(root.left),maxDepth2(root.right))+1;
    }


    /**
     * 559. N 叉树的最大深度
     * https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/
     * 给定一个 N 叉树，找到其最大深度。
     *
     * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
     *
     * N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
     */
    public int maxDepth3(Node root) {
        if(root==null)
            return 0;
        int max = 0;
        if(root.children!=null){
            for(Node child : root.children){
                max = Math.max(max,maxDepth3(child));
            }
        }
        return max+1;
    }
    public int maxDepth4(Node root) {
        if (root == null)   return 0;
        int depth = 0;
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()){
            depth ++;
            int len = que.size();
            while (len-- > 0){
                Node node = que.poll();
                for (int i = 0; i < node.children.size(); i++)
                    if (node.children.get(i) != null)
                        que.offer(node.children.get(i));
            }
        }
        return depth;
    }
}
